{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Steps to Make Array Non-decreasing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #linked-list #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #链表 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: totalSteps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组按非递减顺序排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 。在一步操作中，移除所有满足&nbsp;<code>nums[i - 1] &gt; nums[i]</code> 的 <code>nums[i]</code> ，其中 <code>0 &lt; i &lt; nums.length</code> 。</p>\n",
    "\n",
    "<p>重复执行步骤，直到 <code>nums</code> 变为 <strong>非递减</strong> 数组，返回所需执行的操作数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,3,4,4,7,3,6,11,8,5,11]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>执行下述几个步骤：\n",
    "- 步骤 1 ：[5,<em><strong>3</strong></em>,4,4,7,<em><strong>3</strong></em>,6,11,<em><strong>8</strong></em>,<em><strong>5</strong></em>,11] 变为 [5,4,4,7,6,11,11]\n",
    "- 步骤 2 ：[5,<em><strong>4</strong></em>,4,7,<em><strong>6</strong></em>,11,11] 变为 [5,4,7,11,11]\n",
    "- 步骤 3 ：[5,<em><strong>4</strong></em>,7,11,11] 变为 [5,7,11,11]\n",
    "[5,7,11,11] 是一个非递减数组，因此，返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,5,7,7,13]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>nums 已经是一个非递减数组，因此，返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [steps-to-make-array-non-decreasing](https://leetcode.cn/problems/steps-to-make-array-non-decreasing/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [steps-to-make-array-non-decreasing](https://leetcode.cn/problems/steps-to-make-array-non-decreasing/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,3,4,4,7,3,6,11,8,5,11]', '[4,5,7,7,13]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        stk = []\n",
    "        dp = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cnt = 0\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                cnt += 1\n",
    "                cnt += max(0, dp[stk.pop()] - cnt)\n",
    "            dp[i] = cnt\n",
    "            ans = max(ans, cnt)\n",
    "            stk.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import deque\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        stack = []\n",
    "        top = 0\n",
    "        numlen = len(nums)\n",
    "        time = [numlen for _ in range(numlen)]\n",
    "        deltime = [0 for _ in range(numlen)]\n",
    "        ans = 0\n",
    "        for i in range(numlen):\n",
    "            while top > 0 and nums[stack[top-1]] <= nums[i]:\n",
    "                top -= 1\n",
    "                stack.pop()\n",
    "            while top > 0 and time[stack[top-1]] <= deltime[stack[top-1]]:\n",
    "                top -= 1\n",
    "                stack.pop()\n",
    "            # print(nums[i], stack)\n",
    "            if top > 0:\n",
    "                deltime[stack[top-1]] += 1\n",
    "                time[i] = deltime[stack[top-1]]\n",
    "                ans = max(ans, time[i])\n",
    "            stack.append(i)\n",
    "            top += 1\n",
    "        # print(time)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        leftMaxIndex = -1\n",
    "        stack = [] # 记录左侧索引\n",
    "        n = len(nums)\n",
    "        time = [n for _ in range(n)]\n",
    "        deltaTime = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            # 找到左侧大值\n",
    "            while leftMaxIndex >= 0 and nums[stack[leftMaxIndex]] <= nums[i]:\n",
    "                leftMaxIndex -= 1\n",
    "                stack.pop()\n",
    "            # 找到后判断当前数能否被左侧大值消除，如果不能继续往左寻找\n",
    "            while leftMaxIndex >= 0 and time[stack[leftMaxIndex]] <= deltaTime[stack[leftMaxIndex]]:\n",
    "                leftMaxIndex -= 1\n",
    "                stack.pop()\n",
    "            if leftMaxIndex >= 0:\n",
    "                deltaTime[stack[leftMaxIndex]] += 1\n",
    "                time[i] = deltaTime[stack[leftMaxIndex]]\n",
    "                ans = max(ans, time[i])\n",
    "            stack.append(i)\n",
    "            leftMaxIndex += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        z = []\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            nz = 0\n",
    "            while z and z[-1][0] <= x:\n",
    "                nz = max(nz, z.pop()[1])\n",
    "            nz = nz + 1 if z else 0\n",
    "            ans = max(ans, nz)\n",
    "            z.append((x, nz))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            \n",
    "            max_t += 1\n",
    "            if st:\n",
    "                ans = max(ans, max_t)\n",
    "            st.append((num, max_t))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        stack=[]\n",
    "        for num in nums:\n",
    "            max_times=0\n",
    "            while stack and stack[-1][0]<=num:\n",
    "                max_times=max(max_times,stack.pop()[1])\n",
    "            stack.append((num,max_times+1 if stack else 0))\n",
    "            ans=max(ans,stack[-1][1])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans, st = 0, []\n",
    "        for num in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            ans = max(ans, max_t)\n",
    "            st.append((num, max_t))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        # ans, st = 0, []\n",
    "        # for num in nums:\n",
    "        #     max_t = 0\n",
    "        #     # print(st)\n",
    "        #     while st and st[-1][0] <= num:\n",
    "        #         max_t = max(max_t, st.pop()[1])\n",
    "        #     max_t = max_t + 1 if st else 0  \n",
    "        #     # 如果st为空了，说明前面没有比我更大的数了\n",
    "        #     ans = max(ans, max_t)\n",
    "        #     st.append((num, max_t))\n",
    "            \n",
    "        # return ans\n",
    "        ans = 0\n",
    "        st = []\n",
    "        for x in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= x:\n",
    "                max_t = max(max_t,st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            ans = max(ans,max_t)\n",
    "            st.append((x,max_t))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans, st = 0, []\n",
    "        for num in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            ans = max(ans, max_t)\n",
    "            st.append((num, max_t))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef totalSteps(self, nums: List[int]) -> int:\n",
    "\t\t\n",
    "\t\tans, stack = 0, []\n",
    "\n",
    "\t\tfor num in nums: \n",
    "\t\t\tmax_t = 0\n",
    "\t\t\twhile stack and stack[-1][0] <= num:\n",
    "\t\t\t\tmax_t = max([max_t, stack.pop()[1]])\n",
    "\t\t\tmax_t = max_t + 1 if stack else 0\n",
    "\t\t\tans = max([ans, max_t])\n",
    "\t\t\tstack.append([num, max_t])\n",
    "\n",
    "\t\treturn ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans,st=0,[]\n",
    "        for num in nums:\n",
    "            max_t=0\n",
    "            while st and st[-1][0]<=num:\n",
    "                max_t=max(max_t,st.pop()[1])\n",
    "            st.append((num,max_t+1 if st else 0))\n",
    "            ans=max(ans,st[-1][1])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        s = []\n",
    "        for num in nums:\n",
    "            steps = 0\n",
    "            while s and s[-1][0] <= num:\n",
    "                steps = max(steps, s.pop()[1])\n",
    "            steps = steps + 1 if s else 0\n",
    "            ans = max(ans, steps)\n",
    "            s.append((num, steps))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        root, cntMax, stack = nums[0], 0, []\n",
    "        for x in nums[1:]:\n",
    "            if x >= root:\n",
    "                root = x\n",
    "                while stack:\n",
    "                    cntMax = max(cntMax, stack.pop()[1])\n",
    "            else:\n",
    "                pres = 0\n",
    "                while stack and x >= stack[-1][0]:\n",
    "                    pres = max(pres, stack.pop()[1])\n",
    "                stack.append([x, pres + 1])\n",
    "        while stack:\n",
    "            cntMax = max(cntMax, stack.pop()[1])\n",
    "        return cntMax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            t = 0\n",
    "            while s and s[-1][0] <= nums[i]:\n",
    "                _, v = s.pop()\n",
    "                t = max(t, v)\n",
    "\n",
    "            if s:\n",
    "                s.append([nums[i], t + 1])\n",
    "                ans = max(ans, t + 1)\n",
    "            else:\n",
    "                s.append([nums[i], 0])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        stack = []\n",
    "        for num in nums:\n",
    "            max_tmp = 0\n",
    "            while stack and stack[-1][0] <= num:\n",
    "                max_tmp = max(max_tmp, stack.pop()[1])\n",
    "            max_tmp += 1 if stack else 0\n",
    "            ans = max(ans, max_tmp)\n",
    "            stack.append((num, max_tmp))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans, st = 0, []\n",
    "        for num in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            ans = max(ans, max_t)\n",
    "            st.append((num, max_t))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= n:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            ans = max(ans, max_t)\n",
    "            st.append((n, max_t))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            mx = 0\n",
    "            while st and st[-1][0] <= x:\n",
    "                mx = max(mx, st.pop()[1])\n",
    "            mx = 0 if not st else (mx + 1)\n",
    "            ans = max(mx, ans)\n",
    "            st.append((x, mx))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        # 单调递减栈，存储元素及其被删除的时刻，当遇到一个不小于栈顶的元素x时，就不断弹出栈顶元素，并取出弹出元素被删除时刻的最大值\n",
    "        ans, st = 0, []\n",
    "        for num in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            ans = max(ans, max_t)\n",
    "            st.append((num, max_t))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        res, st = 0, []\n",
    "        for num in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            res = max(res, max_t)\n",
    "            st.append((num, max_t))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        # find the first a[l] > a[cur]\n",
    "\n",
    "        n = len(nums)\n",
    "        left = [0] * n\n",
    "        st = []\n",
    "        for r, x in enumerate(nums):\n",
    "            d = 0\n",
    "            while st and x >= nums[st[-1]]:\n",
    "                d = max(d, left[st.pop()])\n",
    "            if st:\n",
    "                # left[r] = r - st[-1]\n",
    "                left[r] = d + 1\n",
    "            st.append(r)\n",
    "        # print(left)\n",
    "        return max(left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        res, st = 0, []\n",
    "        for num in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            res = max(res, max_t)\n",
    "            st.append((num, max_t))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans, st = 0, []\n",
    "        for num in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            ans = max(ans, max_t)\n",
    "            st.append((num, max_t))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        res,ss = 0,[]\n",
    "        for n in nums:\n",
    "            cur = 0\n",
    "            while ss and ss[-1][0] <= n:\n",
    "                cur = max(cur,ss.pop()[1])\n",
    "            if not ss:\n",
    "                cur = 0\n",
    "            else:\n",
    "                cur += 1\n",
    "            res = max(res,cur)\n",
    "            ss.append([n,cur])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        z = []\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            nz = 0\n",
    "            while z and z[-1][0] <= x:\n",
    "                nz = max(nz, z.pop()[1])\n",
    "            nz = nz + 1 if z else 0\n",
    "            ans = max(ans, nz)\n",
    "            z.append((x, nz))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        stack = []\n",
    "        result = 0\n",
    "        for n in nums:\n",
    "            level = 0\n",
    "            while stack and stack[-1][0] <= n:\n",
    "                level = max(level, stack.pop()[1])\n",
    "            level = level + 1 if stack else 0\n",
    "            result = max(result, level) \n",
    "            stack.append((n, level))\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            mx = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                mx = max(mx, st.pop()[1])\n",
    "            mx = mx + 1 if st else 0\n",
    "            ans = max(ans, mx)\n",
    "            st.append((num, mx))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        stack=[]\n",
    "        ret=0\n",
    "\n",
    "        for i,val in enumerate(nums):\n",
    "            if not stack:\n",
    "                stack.append((val,0))\n",
    "            else:\n",
    "                temp=0\n",
    "                while stack and stack[-1][0]<=val:\n",
    "                    temp=max(temp,stack[-1][1])\n",
    "                    stack.pop()\n",
    "                temp=0 if not stack else temp+1\n",
    "                stack.append((val,temp))\n",
    "                ret=max(ret,temp)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "    还是得好好掌握下线段树\n",
    "'''\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        st = []\n",
    "        for n in nums:\n",
    "            tmp = 0\n",
    "            while st and n >= st[-1][0]:\n",
    "                tmp = max(tmp, st.pop()[1])\n",
    "            tmp = tmp + 1 if st else 0\n",
    "            ans = max(tmp, ans)\n",
    "            st.append([n, tmp])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        stack = []\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            maxVal = 0\n",
    "            while len(stack) > 0 and stack[-1][0] <= num:\n",
    "                maxVal = max(maxVal, stack.pop()[1])\n",
    "            if len(stack):\n",
    "                maxVal += 1\n",
    "            result = max(result, maxVal)\n",
    "            stack.append((num, maxVal))\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        stk = []\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            maxval = 0\n",
    "            while stk and i>=stk[-1][0]:\n",
    "                maxval = max(maxval,stk.pop()[1])\n",
    "            if stk:\n",
    "                maxval += 1\n",
    "            ans = max(ans,maxval)\n",
    "            stk.append((i,maxval))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans, st = 0, []\n",
    "        for num in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            ans = max(ans, max_t)\n",
    "            st.append((num, max_t))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            mx_t = 0\n",
    "            while st and st[-1][0] <= x:\n",
    "                mx_t = max(mx_t,st.pop()[1])\n",
    "            mx_t = mx_t + 1 if st else 0\n",
    "            ans = max(ans,mx_t)\n",
    "            st.append((x,mx_t))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        # 递减栈\n",
    "        down = deque()\n",
    "        res = 0\n",
    "        for num in nums:                        \n",
    "            cnt = 0\n",
    "            while down and down[-1][0] <= num:\n",
    "                cnt = max(cnt,down.pop()[1])                \n",
    "            \n",
    "            if not down:\n",
    "                cnt = 0\n",
    "            else:\n",
    "                cnt += 1\n",
    "                res = max(res,cnt)\n",
    "                          \n",
    "            down.append((num,cnt))\n",
    "                   \n",
    "        while down:\n",
    "            res = max(res,down.pop()[1])\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        st = []\n",
    "        for num in nums:\n",
    "            cnt = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                cnt = max(cnt, st.pop()[-1])\n",
    "            \n",
    "            if st:\n",
    "                cnt += 1\n",
    "                ans = max(ans,cnt)\n",
    "            else:\n",
    "                cnt = 0\n",
    "            st.append((num,cnt))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        # 类似大鱼吃小鱼问题\n",
    "        # 单调递减栈\n",
    "        st = [] # (nums,max_t)，值与被删除时间\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            # 被删除时刻\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t,st.pop()[1])\n",
    "            # 最大的那个元素是没有办法被删除的\n",
    "            if st:\n",
    "                max_t += 1\n",
    "            res = max(max_t,res)\n",
    "            st.append((num,max_t))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans, st = 0, []\n",
    "        for num in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            ans = max(ans, max_t)\n",
    "            st.append((num, max_t))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        monostack = []\n",
    "        monostack.append(0)\n",
    "        dp = [0] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] < nums[monostack[-1]]:\n",
    "                dp[i] = 1\n",
    "                monostack.append(i)\n",
    "            else:\n",
    "                temp = 0\n",
    "                while len(monostack) > 0 and nums[i] >= nums[monostack[-1]]:\n",
    "                    temp = max(dp[monostack[-1]] + 1, temp)\n",
    "                    monostack.pop()\n",
    "                if len(monostack) == 0:\n",
    "                    dp[i] = 0\n",
    "                else:\n",
    "                    dp[i] = temp\n",
    "                monostack.append(i)\n",
    "        return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/steps-to-make-array-non-decreasing/description/\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # https://leetcode.cn/problems/steps-to-make-array-non-decreasing/solutions/1524614/by-endlesscheng-s2yc/\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        if not nums:\n",
    "            return ans\n",
    "\n",
    "        st = []\n",
    "        for num in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            ans = max(ans, max_t)\n",
    "            st.append((num, max_t))\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    for testcase in [\n",
    "        [5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11],\n",
    "        [4, 5, 7, 7, 13],\n",
    "    ]:\n",
    "        ret = s.totalSteps(testcase)\n",
    "        print(\"testcase={}, ret={}\".format(testcase, ret))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        st = []\n",
    "        for x in nums:\n",
    "            mx = 0\n",
    "            while st and st[-1][0] <= x:\n",
    "                mx = max(mx, st.pop()[1])\n",
    "            if st: mx += 1\n",
    "            ans = max(ans, mx)          \n",
    "            st.append((x, mx))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        res, st = 0, []\n",
    "        for num in nums:\n",
    "            max_num = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_num = max(max_num, st.pop()[1]) # 记录删除比它小的数所需步数\n",
    "            max_num = max_num + 1 if st else 0 # 若st为空则证明该数为递增数\n",
    "            res = max(res, max_num) # 更新最大步数\n",
    "            st.append((num, max_num))\n",
    "\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        st = []\n",
    "        ans = 0\n",
    "\n",
    "        for num in nums:\n",
    "            cnt = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                cnt = max(cnt,st.pop()[1])\n",
    "            cnt = cnt + 1 if st else 0\n",
    "            ans = max(ans,cnt)\n",
    "            st.append([num,cnt])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans, st = 0, []  # 初始化最终答案为0，和一个空栈st\n",
    "        for num in nums:\n",
    "            max_t = 0  # 初始化一个变量，用于存储当前元素num需要被移除的次数\n",
    "            # 从栈中移除所有小于或等于当前元素num的元素，并更新max_t\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            # 如果栈非空，增加max_t\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            # 更新最终答案\n",
    "            ans = max(ans, max_t)\n",
    "            # 将当前元素和它的max_t放入栈中\n",
    "            st.append((num, max_t))\n",
    "        return ans  # 返回最终答案\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        st = []\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for num in nums:\n",
    "            maxt = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                maxt = max(maxt,st.pop()[1])\n",
    "            maxt = maxt + 1 if st else 0 \n",
    "            st.append((num,maxt))\n",
    "            ans = max(ans,maxt)\n",
    "\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        st = [] # (x,mx_t)\n",
    "        ans = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            mx_t = 0\n",
    "            while st and st[-1][0] <= x:\n",
    "                mx_t = max(mx_t,st.pop()[1])\n",
    "            if st:\n",
    "                mx_t += 1\n",
    "            ans = max(ans,mx_t)\n",
    "            st.append((x,mx_t))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#使数组按非递减顺序排列，栈，输入：nums = [5,3,4,4,7,3,6,11,8,5,11]输出：3\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans, st = 0, []\n",
    "        for num in nums:\n",
    "            max_t = 0\n",
    "            while st and st[-1][0] <= num:\n",
    "                max_t = max(max_t, st.pop()[1])\n",
    "            max_t = max_t + 1 if st else 0\n",
    "            ans = max(ans, max_t)\n",
    "            st.append((num, max_t))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        stk,ans=[],0\n",
    "        for i in nums:\n",
    "            t=0\n",
    "            while(stk and stk[-1][0]<=i):\n",
    "                t=max(t,stk.pop()[1])\n",
    "            t=t+1 if stk else 0\n",
    "            ans=max(ans,t)\n",
    "            stk.append((i,t))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            mx = 0\n",
    "            while st and st[-1][0] <= x:\n",
    "                mx = max(mx,st.pop()[1])\n",
    "            mx = mx + 1 if st else 0\n",
    "            ans = max(ans,mx)\n",
    "            st.append((x,mx))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import deque\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        stack = []\n",
    "        top = 0\n",
    "        numlen = len(nums)\n",
    "        time = [numlen for _ in range(numlen)]\n",
    "        deltime = [0 for _ in range(numlen)]\n",
    "        ans = 0\n",
    "        for i in range(numlen):\n",
    "            while top > 0 and nums[stack[top-1]] <= nums[i]:\n",
    "                top -= 1\n",
    "                stack.pop()\n",
    "            while top > 0 and time[stack[top-1]] <= deltime[stack[top-1]]:\n",
    "                top -= 1\n",
    "                stack.pop()\n",
    "            # print(nums[i], stack)\n",
    "            if top > 0:\n",
    "                deltime[stack[top-1]] += 1\n",
    "                time[i] = deltime[stack[top-1]]\n",
    "                ans = max(ans, time[i])\n",
    "            stack.append(i)\n",
    "            top += 1\n",
    "        print(time)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        倒叙单调栈\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        stk = [nums[-1]]\n",
    "        stp = [0]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            s = 0\n",
    "            while stk and nums[i] > stk[-1]:\n",
    "                s = max(s+1, stp.pop()) \n",
    "                stk.pop()\n",
    "            stk.append(nums[i])\n",
    "            stp.append(s)\n",
    "        \n",
    "        return max(stp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        dec_win = []\n",
    "        max_t = 0\n",
    "        for i in range(len(nums)):\n",
    "            cur_t = 1\n",
    "            while len(dec_win) > 0 and dec_win[-1][0] <= nums[i]:\n",
    "                cur_t = max(cur_t, dec_win.pop()[1] + 1)\n",
    "            if len(dec_win) == 0:\n",
    "                cur_t = 0\n",
    "            dec_win.append((nums[i], cur_t))\n",
    "            max_t = max(max_t, cur_t)\n",
    "        return max_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n \n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            curMax = 0\n",
    "            while stack and nums[stack[-1]] <= nums[i]:\n",
    "                curMax = max(curMax, dp[stack.pop()])\n",
    "            if stack:\n",
    "                dp[i] = curMax + 1 \n",
    "            stack.append(i)\n",
    "        return max(dp)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        stk = []\n",
    "        for i in range(len(nums)):\n",
    "            t = 0\n",
    "            while stk and nums[stk[-1][0]] <= nums[i]:\n",
    "                t = max(t, stk[-1][1])\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                t += 1\n",
    "            res = max(res, t)\n",
    "            stk.append((i, t))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        post = list(range(1, n+1))\n",
    "        nums.append(10**9+7)\n",
    "\n",
    "        stack = [i-1 for i in range(1, n) if nums[i-1] > nums[i]]\n",
    "        ans = 0\n",
    "        visit = [0]*n\n",
    "        while stack:\n",
    "            ans += 1\n",
    "            nex = []\n",
    "            for i in stack[::-1]:\n",
    "                if nums[i] > nums[post[i]]:\n",
    "                    visit[post[i]] = 1\n",
    "                    post[i] = post[post[i]]\n",
    "            nex = [i for i in stack if not visit[i] and nums[i] > nums[post[i]]]\n",
    "            stack = nex[:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            mx = 0\n",
    "            # print(f'{st}')\n",
    "            while st and st[-1][0] <= x:\n",
    "                mx = max(mx, st.pop()[1])\n",
    "            mx = 0 if not st else (mx + 1)\n",
    "            ans = max(mx, ans)\n",
    "            st.append((x, mx))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        f = [0] * len(nums)\n",
    "        stk = []\n",
    "        for i, x in enumerate(nums):\n",
    "            t = 0\n",
    "            while stk and x >= nums[stk[-1]]:\n",
    "                t = max(t, f[stk.pop()])\n",
    "            f[i] = t + 1 if stk else 0\n",
    "            stk.append(i)\n",
    "        return max(f)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums):\n",
    "        res = 0\n",
    "        stack = []\n",
    "        for num in nums:\n",
    "            max_steps = 0\n",
    "            while stack and stack[-1][0] <= num:\n",
    "                max_steps = max(stack.pop()[1], max_steps)\n",
    "            max_steps += 1 if stack else 0\n",
    "            stack.append((num, max_steps))\n",
    "            res = max(res, max_steps)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "链表模拟的思想也非常巧妙\n",
    "利用了每个元素最多被删除一次的特性，同时从后向前来处理连续删除的情况，避免同一个元素被uoci删除\n",
    "'''\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums.append(inf) # let every nums[i] has `next`\n",
    "        n = len(nums)\n",
    "        nexts = [-1] * n\n",
    "        pres = []\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            nexts[i] = i + 1\n",
    "            if i > 0 and nums[i - 1] > nums[i]: pres.append(i-1)\n",
    "        \n",
    "        while pres:\n",
    "            ans +=1\n",
    "            pres2 = []\n",
    "            \n",
    "            for i in pres:\n",
    "                old=nexts[i]\n",
    "                if  nums[i] > nums[nexts[i]]:\n",
    "                    nexts[i] = nexts[nexts[i]]\n",
    "                    if len(pres2)>0 and old==pres2[-1]:\n",
    "                        pres2[-1]=i\n",
    "                    else:\n",
    "                        pres2.append(i)\n",
    "            pres = pres2\n",
    "        return ans - 1 if ans != 0 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def totalSteps(self, nums: List[int]) -> int:\r\n",
    "        res = 0 \r\n",
    "        st = []\r\n",
    "        for i, x in enumerate(nums):\r\n",
    "            cur = 0 \r\n",
    "            while st and x >= nums[st[-1][0]]:\r\n",
    "                cur = max(cur, st[-1][1])\r\n",
    "                st.pop()\r\n",
    "            if st:\r\n",
    "                cur += 1\r\n",
    "                # print(i, \": \", st, x, nums[st[-1]],x >= nums[st[-1]])\r\n",
    "            res = max(res, cur)\r\n",
    "            st.append((i, cur))\r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        res,st = 0,[]\n",
    "        for idx,i in enumerate(nums):\n",
    "            if not st or st[0][0] <= i:\n",
    "                st = [(i,0)]\n",
    "            else:\n",
    "                temp = st[0][1] + 1\n",
    "                while st[-1][0] <= i:\n",
    "                    _,n = st.pop()\n",
    "                    temp = max(temp,n+1)\n",
    "                st.append((i,temp))\n",
    "                res = max(res,temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n \n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            curMax = 0\n",
    "            while stack and nums[stack[-1]] <= nums[i]:\n",
    "                curMax = max(curMax, dp[stack.pop()])\n",
    "            if stack:\n",
    "                dp[i] = curMax + 1 \n",
    "            stack.append(i)\n",
    "        return max(dp)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        f = [0]*n \n",
    "        big = -1\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num>=big:\n",
    "                f[i] = 0\n",
    "                big = num\n",
    "                stack.clear()\n",
    "            else:\n",
    "                if num < nums[i-1]:\n",
    "                    f[i] = 1\n",
    "                    stack.append((nums[i-1], f[i-1]) )\n",
    "                else:\n",
    "                    f[i] = f[i-1] + 1\n",
    "                    while stack and num >= stack[-1][0]:\n",
    "                        f[i] = max(f[i], stack[-1][1]+1)\n",
    "                        stack.pop()\n",
    "        \n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def totalSteps(self, nums: List[int]) -> int:\n",
    "#         n = 1\n",
    "#         number = 0 \n",
    "#         temp = nums.copy()\n",
    "#         while True:\n",
    "#             number1 = 0\n",
    "#             for i in range(1,len(nums)):\n",
    "#                 if nums[i]<nums[i-1]:\n",
    "#                     temp.pop(i-number1)\n",
    "#                     number1 = number1 + 1   \n",
    "#                     n = 0\n",
    "#             nums = temp.copy()       \n",
    "#             if n==1:\n",
    "#                 break\n",
    "#             n = 1\n",
    "#             number = number + 1\n",
    "#         return number\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * n\n",
    "        big = -1 #目前为止遍历到的最大的数\n",
    "        st = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if num >= big: #当前数是最大的\n",
    "                st.clear()\n",
    "                big = num\n",
    "                f[i] = 0\n",
    "            else:\n",
    "                if num < nums[i-1]: #当前数小于前一个数，说明之前序列递增\n",
    "                    f[i] = 1\n",
    "                    st.append((nums[i-1], f[i-1]))\n",
    "                else: #否则，当前数处于递增序列中，需要与之前递增序列的最大数比较\n",
    "                    f[i] = f[i-1] + 1\n",
    "                    while st and st[-1][0] <= num:\n",
    "                        f[i] = max(f[i], st[-1][1] + 1)\n",
    "                        st.pop()\n",
    "        return max(f)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nxt = [0] * n\n",
    "        vec = []\n",
    "        vec2 = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            nxt[i] = i+1\n",
    "            if i+1 < n and nums[i] > nums[i+1]:\n",
    "                vec.append(i)\n",
    "        # print(nxt)\n",
    "        ans = 0\n",
    "        while vec:\n",
    "            ans+=1\n",
    "            for x in vec:\n",
    "                old = nxt[x]\n",
    "                # print(x,nxt[x])\n",
    "                nxt[x] = nxt[nxt[x]]\n",
    "\n",
    "                if nxt[x] < n and nums[x] > nums[nxt[x]]:\n",
    "                    if len(vec2)>0 and vec2[-1]==old:\n",
    "                        vec2[-1] = x\n",
    "                    else:\n",
    "                        vec2.append(x)\n",
    "            vec = []\n",
    "            vec,vec2 = vec2,vec\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        f = [0]*n \n",
    "        big = -1\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num >= big:\n",
    "                stack.clear()\n",
    "                f[i] = 0\n",
    "                big = num\n",
    "            else:\n",
    "                if num >= nums[i-1]:\n",
    "                    f[i] = f[i-1] + 1\n",
    "                    while stack and stack[-1][0] <= num:\n",
    "                        f[i] = max(f[i], stack[-1][1]+1)\n",
    "                        stack.pop()\n",
    "                else:\n",
    "                    f[i] = 1\n",
    "                    stack.append( (nums[i-1], f[i-1]) )\n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * n\n",
    "        big = -1 #目前为止遍历到的最大的数\n",
    "        st = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if num >= big: #当前数是最大的\n",
    "                st.clear()\n",
    "                big = num\n",
    "                f[i] = 0\n",
    "            else:\n",
    "                if num < nums[i-1]: #当前数小于前一个数，说明之前序列递增\n",
    "                    f[i] = 1\n",
    "                    st.append((nums[i-1], f[i-1]))\n",
    "                else: #否则，当前数处于递增序列中，需要与之前递增序列的最大数比较\n",
    "                    f[i] = f[i-1] + 1\n",
    "                    while st and st[-1][0] <= num:\n",
    "                        f[i] = max(f[i], st[-1][1] + 1)\n",
    "                        st.pop()\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cnt = 0\n",
    "            while stk and stk[-1][0] < nums[i]:\n",
    "                cnt += 1\n",
    "                cnt += max(0, stk.pop()[1] - cnt)\n",
    "            ans = max(ans, cnt)\n",
    "            stk.append((nums[i], cnt))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cnt = 0\n",
    "            while stk and stk[-1][0] < nums[i]:\n",
    "                cnt += 1\n",
    "                cnt += max(0, stk.pop()[1] - cnt)\n",
    "            ans = max(ans, cnt)\n",
    "            stk.append((nums[i], cnt))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        s = []\n",
    "        ans = 0\n",
    "        for j in nums[::-1]:\n",
    "            t = 0\n",
    "            while s and (j>s[-1][0]):\n",
    "                tmp = s.pop()\n",
    "                t+=1 \n",
    "                if tmp[1]>0: \n",
    "                    t = max(t, tmp[1]) \n",
    "            ans = max(ans, t)\n",
    "            # if s:\n",
    "            #     s[-1][1] = t + 1\n",
    "            s.append([j, t])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        s = []\n",
    "        for val in nums[::-1]:\n",
    "            cnt = 0\n",
    "            while s and s[-1][0] < val:\n",
    "                cnt = max(cnt+1, s.pop()[1])\n",
    "            s.append([val, cnt])\n",
    "\n",
    "        return max(cnt for _, cnt in s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        s = []\n",
    "        for num in nums[::-1]:\n",
    "            cnt = 0\n",
    "            while s and s[-1][0]<num:\n",
    "                cnt = max(cnt+1,s.pop()[-1])\n",
    "            s.append([num,cnt])\n",
    "        return max(cnt for _,cnt in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        st = []\n",
    "        for v in nums[::-1]:\n",
    "            cur = 0\n",
    "            while st and st[-1][0] < v:\n",
    "                cur = max(cur+1, st.pop()[1])\n",
    "            st.append([v, cur])\n",
    "        return max(v for _, v in st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        s = []\n",
    "        for a in nums[::-1]:\n",
    "            cnt = 0\n",
    "            while s and s[-1][0] < a:\n",
    "                cnt = max(cnt + 1, s.pop()[1])\n",
    "            s.append([a, cnt])\n",
    "        return max(cnt for _, cnt in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        l = []\n",
    "        n = len(nums)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = 0\n",
    "\n",
    "            while l and l[-1][0] < nums[i]:\n",
    "                    _,t = l.pop()\n",
    "                    if t > x:\n",
    "                        x = t\n",
    "                    else:\n",
    "                        x += 1\n",
    "            l.append([nums[i],x])\n",
    "        ans = 0\n",
    "        for i in l:\n",
    "            ans = max(ans,i[1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            cnt = 0\n",
    "            while stack and stack[-1][0] < nums[i]:\n",
    "                cnt = max(cnt+1, stack.pop()[1])\n",
    "            stack.append([nums[i],cnt])\n",
    "        return max(item[1] for item in stack)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cur_loop = 0\n",
    "            while stack and stack[-1][0] < nums[i]:\n",
    "                tmp = stack.pop()\n",
    "                cur_loop = max(cur_loop + 1, tmp[1])\n",
    "            stack.append([nums[i], cur_loop])\n",
    "            ans = max(ans, cur_loop)\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            cnt = 0\n",
    "            while stack and stack[-1][0] < nums[i]:\n",
    "                _, x = stack.pop()\n",
    "                cnt = cnt + 1 if cnt + 1 > x else x\n",
    "            stack.append([nums[i], cnt])\n",
    "        return max(ls[1] for ls in stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "        stk = []\n",
    "        ret = 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            cnt = 0\n",
    "            while stk and nums[stk[-1][0]] < nums[i]:\n",
    "                idx, v = stk.pop()\n",
    "                cnt = max(cnt + 1, v)\n",
    "            ret = max(ret, cnt)\n",
    "            stk.append((i, cnt))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalSteps(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            cnt = 0\n",
    "            while stack and nums[stack[-1][0]] < nums[i]:\n",
    "                _, c = stack.pop()\n",
    "                cnt = cnt + 1 if cnt + 1 > c else c\n",
    "            stack.append([i, cnt])\n",
    "        return max(ans[1] for ans in stack)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
